/**
 * @ClassName Queue
 * @Description TODO
 * @Author Quentin_zyj
 * @Date 2021/11/3 15:41
 */
public class Queue {
    // 皇后个数
    static int n;
    // 当前解, x[i]代表第x[i]行第i列(所以x数组长度为棋盘长度n+1(下标从1开始))
    static int[] x;
    // 当前已找到的可行方案数
    static int sum;

    // 合法性检验
    static boolean place(int k) {
        for (int j = 1; j < k; j++) {
            // 前者判断是否处于一条斜线上, 后者判断是否有列冲突。
            // 因为已经把棋盘压缩到一个一维数组, 每一行在数组中占一个元素的位置, 所以不会存在行冲突
            if ((Math.abs(k - j) == Math.abs(x[j] - x[k])) || (x[j] == x[k])) {
                return false;
            }
        }
        return true;
    }

    static void back(int t) {
        if (t > n)
            sum++;
        else {
            for (int i = 1; i <= n; i++) {
                x[t] = i;
                if (place(t)) {
                    back(t + 1);
                }
            }
        }
    }
}
